package com.wx.algorithm;

import com.wx.CommonUtils;

public class Sort {

    /**
     * 选择法
     *
     * @return
     */
    public static int[] selectMethod(int[] origin) {
        if (origin.length == 0) {
            return origin;
        }
        for (int i = 0; i < origin.length - 1; i++) {
            for (int j = i + 1; j < origin.length; j++) {
                if (origin[i] > origin[j]) {
                    int temp = origin[i];
                    origin[i] = origin[j];
                    origin[j] = temp;
                }
            }
        }
        return origin;
    }

    /**
     * 插入法
     *
     * @param arr
     */
    public static int[] insertionMethod(int[] arr) {
        int index = 1;
        while (index < arr.length) {
            int temp = arr[index];
            for (int j = index - 1; j >= 0; j--) {
                if (arr[j] > temp) {
                    arr[j + 1] = arr[j];
                    arr[j] = temp;
                }
            }
            index++;
        }
        return arr;
    }

    /**
     * 冒泡法
     * O(n2)
     *
     * @param arr
     * @return
     */
    public static int[] bubbling(int[] arr) {

        for (int i = 0; i < arr.length; i++) {
            for (int j = arr.length - 1; j > i; j--) {
                if (arr[j] < arr[j - 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j - 1];
                    arr[j - 1] = temp;
                }
            }
        }
        return arr;
    }

    /**
     * 快速排序
     *
     * @param arr
     * @return
     */
    public static int[] fastSort1(int[] arr, int begin, int end) {
        int midIndex;
        if (end - begin >= 2) {
            midIndex = begin;
            begin = begin + 1;
        } else if (end - begin == 1) {
            if (arr[begin] > arr[end]) {
                int temp = arr[begin];
                arr[begin] = arr[end];
                arr[end] = temp;
            }
            return arr;
        } else {
            return arr;
        }
        int endIndex = end;

        while (begin <= end) {
            if (arr[midIndex] > arr[end] && end > midIndex) {
                //把调换值并修改指针记录
                int temp = arr[midIndex];
                arr[midIndex] = arr[end];
                arr[end] = temp;
                midIndex = end;
                end--;
            } else {
                while (arr[midIndex] <= arr[end] && end >= begin) {
                    //先从后往前找比中间量小的
                    end--;
                }
                if (arr[midIndex] > arr[end] && end > midIndex) {
                    //把调换值并修改指针记录
                    int temp = arr[midIndex];
                    arr[midIndex] = arr[end];
                    arr[end] = temp;
                    midIndex = end;
                    end--;
                }
            }

            if (arr[midIndex] < arr[begin] && begin < midIndex) {
                //把调换值并修改指针记录
                int temp = arr[midIndex];
                arr[midIndex] = arr[begin];
                arr[begin] = temp;
                midIndex = begin;
                begin++;
            } else {
                while (arr[midIndex] >= arr[begin] && end >= begin) {
                    begin++;
                }
                if (arr[midIndex] < arr[begin] && begin < midIndex) {
                    //把调换值并修改指针记录
                    int temp = arr[midIndex];
                    arr[midIndex] = arr[begin];
                    arr[begin] = temp;
                    midIndex = begin;
                    begin++;
                }
            }
        }
        //右边排序
        fastSort1(arr, 0, midIndex - 1);
        fastSort1(arr, midIndex + 1, endIndex);
        return arr;
    }

    public static int[] QuickSort(int arr[], int begin, int end) {
        int temp = arr[begin];
        int i = begin;
        int j = end;

        if (j > i) {
            while (j != i) {
                while (j > i && arr[j] >= temp) {
                    --j;
                }
                if (j > i) {
                    arr[i] = arr[j];
                    i++;
                }

                while (j > i && arr[i] <= temp) {
                    i++;
                }
                if (j > i) {
                    arr[j] = arr[i];
                    j--;
                }
            }
            arr[i] = temp;
            QuickSort(arr, begin, i - 1);
            QuickSort(arr, i+1, end);
        }
        return arr;
    }


    public static void main(String[] args) {
        CommonUtils.printArr(bubbling(new int[]{1, 5, 8, 2, 4, 6}));
        CommonUtils.printArr(insertionMethod(new int[]{1, 5, 8, 2, 4, 6}));

        int[] arr = new int[]{5, 1, 8, 9, 10, 15, 1, 4};
        int begin = 0;
        int end = arr.length - 1;
//        CommonUtils.printArr(fastSort(arr, begin, end));
        CommonUtils.printArr(QuickSort(arr, begin, end));
    }
}
